package leetcode;

import java.util.Stack;

class LeetCode {
    //面试题 02.04. 分割链表
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public ListNode partition(ListNode head, int x) {
        // 边界
        if(head == null) {
            return null;
        }
        ListNode smallHead = new ListNode(101);
        ListNode smallTail = smallHead;
        ListNode bigHead = new ListNode(101);
        ListNode bigTail = bigHead;
        // 遍历原链表
        while (head != null) {
            if (head.val < x) {
                // 尾插入小链表
                smallTail.next = head;
                smallTail = head;
            }else {
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        // 拼接大小链表
        bigTail.next = null;
        smallTail.next = bigHead.next;
        return smallHead.next;
    }
}

/**class LeetCode {
   //num203移除链表元素
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode removeElements(ListNode head, int val) {

        while(head!=null&&head.val==val) {
            head = head.next;
        }
        if(head==null)
        {
            return null;
        }

        else
        {
            ListNode prev=head;
            while(prev.next!=null)
            {
                if(prev.next.val==val) {

                    prev.next=prev.next.next;

                }
                else
                {
                    prev=prev.next;
                }
            }

        }
        return head;
    }
}
*/
    /**
{
//num160相交链表
public class ListNode {
int val;
      ListNode next;
             ListNode(int x) {
                 val = x;next = null;
              }
          }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA=headA;
        ListNode pB=headB;
        while(pA!=pB)
        {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}*/
 /**
{//num876中间节点
    public class ListNode {
     int val;
     ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
    public ListNode middleNode(ListNode head) {
        ListNode fast=head;
        ListNode low=head;
        while(fast!=null&&fast.next!=null)
        {
            low=low.next;
            fast=fast.next.next;
        }
        return low;
    }
}*/
    /**
{   //num19 删除倒数第K个节点
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head,low = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        // 此时再让low和fast同时向后移动，直到fast为空
        while (fast != null) {
            low = low.next;
            fast = fast.next;
        }
        return low;
    }

    public class ListNode {
     int val;ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
        }*/

/** //num20 有效的括号
public class LeetCode {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] charArray = s.toCharArray();

        for (char ch : charArray) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (!stack.isEmpty()) {
                    if (ch == ')') {
                        if (stack.pop() != '(')
                            return false;
                    } else if (ch == '}') {
                        if (stack.pop() != '{')
                            return false;
                    } else {
                        if (stack.pop() != '[')
                            return false;
                    }
                }
                else{
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}*/
